package kyssion.leetcode.num101_150;

import java.util.ArrayList;
import java.util.List;

public class code139_单词拆分 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");
        list.add("pens");
        System.out.println(new code139_单词拆分().wordBreak(
                "applepenapple", list
        ));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }
        boolean dp[] = new boolean[s.length()];
        for (int a = 0; a < s.length(); a++) {
            for (String s1 : wordDict) {
                if (a >= s1.length() - 1 &&
                        s.substring(a - s1.length() + 1, a + 1).equals(s1)) {
                    if (a - s1.length() + 1 == 0) {
                        dp[a] = true;
                    } else {
                        dp[a] = dp[a] || dp[a - s1.length()];
                    }
                }
            }
        }
        return dp[s.length() - 1];
    }
}
